#include <stdio.h>
#include <string.h>

/*
 * 折半查找算法
 * 
 *		一半一半的查找，不过前提必须是一个有序的序列，且折半查找需要先对数据进行排序。
 *
 *	复杂度分析：
 *
 *		折半查找就像搜素二叉树：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。
 *		折半查找法的查找次数正好为该值所在的层数。
 *		等概率情况下，约为log2(n+1)-1，其算法复杂度为O(log(n))。
 */

/*
 * 递归实现
 *
 *	ac[]	: 要进行查找的数组
 *	key		: 要进行查找的数值
 *	low		: 最小下标
 *	high	: 最大下标
 */

int binary_search_recursion(int low, int high, int key, int ac[])
{
	int mid = (low + high) >> 1;		/* 取中间值 */
	//printf("mid = %d\n", mid);
	//printf("=== %d %d\n", low, high);

	if ( low > high) {
		return -1;
	}

	if (key == ac[mid]) {	
		return mid;
	}
	else if (key > ac[mid]) {
		//printf("mid = %d\n", mid+1);
		//printf("> %d %d\n", low, high);
		return binary_search_recursion(mid + 1, high, key, ac);
	}
	else if (key < ac[mid]) {
		//printf("mid = %d\n", mid-1);
		//printf("< %d %d\n", low, mid-1);
		return binary_search_recursion(low, mid - 1, key, ac);	/* 当先>执行后变成<时，low的值会被改mid+1，查找55时就是例子 */
	}
}

/*
 * 顺序实现
 *
 *	ac[]	: array
 *	key		: find value
 *  low		: minimum subscript
 *	high	: maximum subscript
 */
int binary_search_order(int low, int high, int key, int ac[])
{
	int mid = -1;

	if (low > high) {
		return -1;
	}

	while (low <= high) {
		mid = (low + high) >> 1;

		if (key == ac[mid]) {
			return mid;
		}
		else if (key > ac[mid]) {
			low = mid + 1;
		}
		else if (key < ac[mid]) {
			high = mid - 1;
		}
	}

	return -1;
}

void main_recursion()
{
	int array[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
	int brray[11] = {1, 1, 1, 1, 1, 1, 1, 21, 34, 55, 89};
	int index = -1;

#if 1
	index = binary_search_recursion(0, 11, 55, array);	// mid = (5, 8, 10, 9)
	printf("index = %d\n", index);		// 9
#endif
#if 0
	index = binary_search_recursion(0, 11, 1, array);		// min value, mid = (5, 2, 0)
	printf("index = %d\n", index);		// 0
#endif
#if 0
	index = binary_search_recursion(0, 11, 89, array);	// max value, mid = (5, 8, 10)
	printf("index = %d\n", index);		// 10

#endif
#if 0
	index = binary_search_recursion(0, 11, 1, brray);	
	printf("index = %d\n", index);		// 5	如果有相同的元素，并不会是第一个，因为是折半的，所以谁出现在折半的点上，谁被输出下标

	index = binary_search_recursion(0, 11, 25, brray);	
	printf("index = %d\n", index);		// -1

	index = binary_search_recursion(0, 11, 0, brray);	
	printf("index = %d\n", index);		// -1
#endif
}

void main_order()
{
	int array[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
	int brray[11] = {1, 1, 1, 1, 1, 1, 1, 21, 34, 55, 89};
	int index = -1;

	index = binary_search_order(0, 11, 55, array);	
	printf("index = %d\n", index);		
}

void main()
{
	//main_recursion();
	main_order();
}
